package exer;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;

/**
 * @Author 比特就业课
 * @Date 2022-10-20
 */
public class BinaryTree {
    // 定义一个表示节点的类
    public static void main(String[] args) {
        BinaryTree binaryTree = new BinaryTree();
        binaryTree.create();
        binaryTree.preOrder(root);
        System.out.println();
        binaryTree.inOrder(root);
        System.out.println();
        binaryTree.postOrder(root);
        System.out.println();
        System.out.println("**********************");
        System.out.println(binaryTree.getLeafNodeCount(root));
        System.out.println("********************");
        System.out.println(binaryTree.size(root));
        System.out.println(binaryTree.size1(root));
        binaryTree.getLeafNodeCounts(root);
        System.out.println(counts);
        System.out.println(binaryTree.getKLevelNodeCount(root, 1));
        System.out.println(binaryTree.find(root, 5));
        System.out.println(binaryTree.isCompleteTree(root));
        System.out.println("***************************");
        binaryTree.levelOrder(root);
    }
    private static class TreeNode {
        int value; // 当前节点的值
        TreeNode left;  // 左子树的引用
        TreeNode right; // 右子树的引用
        // 构造方法

        public TreeNode(int value) {
            this.value = value;
        }

        @Override
        public String toString() {
            return "TreeNode{" +
                    "value=" + value +
                    '}';
        }
    }



    // 根节点的引用
    public static TreeNode root;
    public static int count;
    public static int leftCount;
    public static int numSize;

    /**
     * 为了演示方便通过硬代码的方式创建一个二叉树
     * 后续不会通过这样的方式去创建二叉树
     */

    public void create () {
        // 先所有的节点创建出来
        TreeNode node1 = new TreeNode(1);
        TreeNode node2 = new TreeNode(2);
        TreeNode node3 = new TreeNode(3);
        TreeNode node4 = new TreeNode(4);
        TreeNode node5 = new TreeNode(5);
        TreeNode node6 = new TreeNode(6);
        TreeNode node7 = new TreeNode(7);
        TreeNode node8 = new TreeNode(8);
        // 处理引用关系
        node1.left = node2;
        node1.right = node3;
        node2.left = node4;
        node2.right = node5;
       node5.right = node8;
        node3.left = node6;
        node3.right = node7;
        // 指定根节点的引用
        root = node1;
    }

    // 前序遍历
    public void preOrder(TreeNode root) {
        //判断该结点是否为空
        if(root==null){
            return;
        }
        System.out.print(root.value+" ");
        preOrder(root.left);
        preOrder(root.right);

    }

    // 中序遍历
    public void inOrder(TreeNode root) {
       if(root==null){
           return;
       }
       inOrder(root.left);
        System.out.print(root.value+" ");
       inOrder(root.right);

    }

    // 后序遍历
    public void postOrder(TreeNode root) {
        //1.判断是否为空
        if(root==null){
            return;
        }
        //处理左子节点
        postOrder(root.left);
        //处理右子节点
        postOrder(root.right);
        System.out.print(root.value+" ");

    }
    //遍历思路求结点个数
public int size1(TreeNode root){
        //判断树是否为空
        if(root==null){
            return 0;
        }
        numSize++;
        size1(root.left);
        size1(root.right);
   return numSize;
}
    // 获取树中节点的个数(子问题思路)
    public int size(TreeNode root) {
        if(root==null){
            return 0;
        }

        return size(root.left)+size(root.right)+1;
    }

    // 获取叶子节点的个数
    public int getLeafNodeCount(TreeNode root) {
      //判断结点是否为空
        if(root==null){
            return 0;
        }
        //判断是否为叶子结点
        if(root.left==null&&root.right==null){
            return 1;
        }
        return getLeafNodeCount(root.left)+getLeafNodeCount(root.right);

    }
static int counts;
// 遍历思路-求叶子结点个数
public void getLeafNodeCounts(TreeNode root) {
    if(root==null){
        return ;
    }
    if(root.left==null&&root.right==null){
        counts++;
    }
    getLeafNodeCounts(root.left);
    getLeafNodeCounts(root.right);

}


    // 获取第K层节点的个数
    public int getKLevelNodeCount(TreeNode root,int k) {
    if(k<=0){
        return 0;
    }
    if(root==null){
        return 0;
    }
    //向下遍历
        if(k==1){
            return 1;
        }
        return getKLevelNodeCount(root.left,k-1)+getKLevelNodeCount(root.right,k-1);


    }

    // 获取二叉树的高度
// https://leetcode.cn/problems/er-cha-shu-de-shen-du-lcof/submissions/375238559/
    public int getHeight(TreeNode root) {
    //判断根结点
        if(root==null){
            return 0;
        }
        return Math.max(getHeight(root.left),getHeight(root.right))+1;
    }

    // 检测值为value的元素是否存在
    static TreeNode temp=null;
    public TreeNode find(TreeNode root, int val) {
        if(root==null){
            return null;
        }
        if(root.value==val){
            temp=root;
            return temp;
        }
        find(root.left,val);
        find(root.right,val);
        return temp;

    }
    //运用子问题思路
    public TreeNode find1(TreeNode root, int val) {
        if(root==null){
            return null;
        }
        if(root.value==val){
            return root;
        }
       if(find1(root.left,val)!=null){
           return root.left;
       }
       else{
           return find1(root.right,val);
       }

    }

    //层序遍历
    public void levelOrder(TreeNode root) {
        //判断根结点是否为空
        if(root==null){
            return ;
        }
        //创建队列来储存节点
        Queue<TreeNode>queue=new LinkedList<>();
        queue.offer(root);
        //判断队列是否为空
        while(!queue.isEmpty()){
            TreeNode cur=queue.poll();
            System.out.print(cur+" ");
            if(cur.left!=null){
                queue.offer(cur.left);
            }
            if(cur.right!=null){
                queue.offer(cur.right);
            }
        }

    }

    // 判断一棵树是不是完全二叉树
    public boolean isCompleteTree(TreeNode root) {
        //对根节点进行判断
        if(root==null){
            return true;
        }
        //建立队列
    Queue<TreeNode>queue=new LinkedList<>();
        //将根结点入队
        queue.offer(root);
        while (!queue.isEmpty()){
            TreeNode cur=queue.poll();
            if(cur==null){
                break;
            }
            //将其左右节点入队
            queue.offer(cur.left);
            queue.offer(cur.right);
        }
        //如果队列不是空的,不断出队直至为空
        while(!queue.isEmpty()){
            if(queue.poll()!=null){
                return false;
            }
        }
        return true;


    }
}
